Design engineers design IC's by transforming circuit description of the IC's into geometric descriptions, called layouts. To create layouts, design engineers typically use electronic design automation (“EDA”) applications. These applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts. EDA applications create layouts by using geometric shapes that represent different materials and devices on IC's. For instance, EDA tools commonly represent IC components as rectangular objects. They also use rectangles to represent horizontal and vertical interconnections between rectangular IC components. The horizontal and vertical interconnects are referred to as Manhattan interconnects or wiring.
EDA tools typically represent a rectangular object in terms of x and y coordinates of two opposing vertices of the object (i.e., in terms of xLO, yLO, and xHI, yHI). These tools often represent a non-rectangular object in terms of the x- and y-coordinates of the object's vertices. Such an approach works well when most of the shapes in the layout are rectangular.
However, certain EDA tools have recently been proposed that support non-Manhattan wiring. These tools often utilize a large number of non-rectangular shapes. The traditional approach of specifying a shape in terms of the coordinates of two or more of its vertices is not efficient for these newer EDA tools. Therefore, there is a need for a novel way of specifying items in a design layout that has non-rectangular shapes.
There is also a need for an efficient way of representing routes with non-Manhattan edges. One prior technique for representing a Manhattan route specifies the route in terms of a set of segments and one or more styles. Each segment is a straight line that connects two points in the design layout. In some cases, the segments of a route are run-length encoded. This encoding specifies a direction and a length for each segment. In such prior encoding, a segment's direction can be along 0°, 90°, 180°, and 270°. This encoding also specifies an order for the segments of the route.
Each segment's style specifies four values that can be used to transform a line-representation of the segment into a rectangular shape that is a more complete geometric representation of the segment. These four values include two low delta values, dxLO and dyLO, and two high delta values, dxHI, and dyHI. The low delta values are subtracted from the segment's lowest x- and y-values xLO, yLO to obtain the low x- and y-values (xRecLO, yRecLO) of rectangle that represents the segment, while the high delta values are added to the segment's highest x- and y-values xHI, yHI to obtain the high x- and y-values (xRecHI, yRecHI) of the rectangle. FIG. 1 illustrates an example of constructing the rectangle for a segment from the coordinates and style values of the segment. This prior technique, however, does not support non-Manhattan routes. Accordingly, there is a need for an efficient representation of routes that can have non-Manhattan edges.